package tree;

public class Tree {
    private static TreeNode buildTree() {
        // 定义结点
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');
        TreeNode i = new TreeNode('I');
        TreeNode j = new TreeNode('J');
        TreeNode k = new TreeNode('K');
        TreeNode l = new TreeNode('L');
        TreeNode m = new TreeNode('M');
        TreeNode n = new TreeNode('N');
        TreeNode o = new TreeNode('O');
        TreeNode p = new TreeNode('P');
        TreeNode q = new TreeNode('Q');

        // 定义结点之间的关系
        a.left = o;
        a.right = b;
        b.right = c;
        c.left = d;
        c.right = e;
        d.left = f;
        d.right = g;
        e.right = h;
        g.left = i;
        g.right = j;
        l.right = k;
        m.left = l;
        o.left = p;
        o.right = q;
        q.left = m;
        q.right = n;
        System.out.println();

        // 返回根结点
        return a;
    }

    static void perOrder(TreeNode root) {
        if (root == null) return;
        System.out.printf("%c ", root.val); // 第一次遇到就操作
        perOrder(root.left);
        perOrder(root.right);
    }

    static void inOrder(TreeNode root) {
        if (root == null) return;
        perOrder(root.left);
        System.out.printf("%c ", root.val);// 第2次遇到操作
        perOrder(root.right);
    }

    static void postOrder(TreeNode root) {
        if (root == null) return;
        perOrder(root.left);
        perOrder(root.right);
        System.out.printf("%c ", root.val); // 第3次遇到操作
    }

    public static void main(String[] args) {
        TreeNode treeNode = buildTree();
        System.out.println();
        perOrder(treeNode);
        System.out.println();
        inOrder(treeNode);
        System.out.println();
        postOrder(treeNode);
        System.out.println();
        System.out.println(leaf(treeNode));
        ans = 0;
        orderLeaf(treeNode);
        System.out.println(ans);
    }
    static int ans = 0;
    public static  void orderLeaf(TreeNode root){
        if(root == null) return;
        if(root.left == null && root.right == null){
            ans += 1;
        }
        orderLeaf(root.left);
        orderLeaf(root.right);
    }

    public static int leaf(TreeNode root) {
        if (root == null)  return 0;
        if(root.left == null && root.right == null) return 1;
        return leaf(root.left) + leaf(root.right);
    }

    public static TreeNode find(TreeNode root,int target){
        if(root == null) return null;
        if(root.val == target) return  root;
        TreeNode left_find = find(root.left,target);
        if(left_find != null) return left_find;
        return find(root.right,target);
    }

    boolean isMirror(TreeNode p, TreeNode q){
        if((p == null && q != null) || (p != null && q == null )) return false;
        if(p == null && q == null) return true;
        return p.val == q.val && isMirror(p.left,q.right) && isMirror(p.right,q.left);
    }
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}